package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;

import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
		Given a binary tree, return the inorder traversal of its nodes' values.
	
	For example:
	Given binary tree [1,null,2,3],
	
	   1
	    \
	     2
	    /
	   3
	
	return [1,3,2]. 
题目大意
	　中序遍历
解题思路
	中序遍历。。
	法一：递归式：so easy~~~
	法二：栈：
	用栈中序遍历没有先序遍历那么直观，因为我们不能马上pop出当前元素，
		而要先把它的左子树都遍历完才能pop它自己。
		所有我们先将将最左边的所有节点都push进栈，然后再依次pop并记录值，
		每pop一个元素后再看它有没有右子树，如果有的话，我们再将它的右节点和右子树中最左边的节点都push进栈，再依次pop。
 * @Date 2017-10-10 17：14
 */
public class _094_Binary_Tree_Inorder_Traversal {
    List<Integer> rs = new ArrayList<>();
    
    
    /**
     * 法一：so~easy
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null)   return rs;
        run(root);
        return rs;
    }
    private void run(TreeNode root) {
        if (root == null)   return;
        run(root.left);
        rs.add(root.val);
        run(root.right);
    }
	public static void main(String[] args) {
		_094_Binary_Tree_Inorder_Traversal obj = new _094_Binary_Tree_Inorder_Traversal();

	}

}
